1. Two Sum

我們挑選 LeetCode 中的 1. Two Sum 作為我們實作練習的第一題，這個題目也是很多人進入 LeetCode 題目中的第一個題目。

比起一題解完就換下一題這樣的方式，我們更建議花多一點在一個題目中，盡可能地持續迭代、持續優化並且思考沈澱，讓你從一個題目掌握到更深更廣的效益。因此我們建議在進入「一個題目」的解題過程時，可以將解題過程分成四個階段，這裡我們就先從「#動手之前先思考」這個步驟開始：

先看一下題目描述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

再搭配範例理解題目

• Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

• Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

這個題目很直觀，從 nums 中找出兩數相加等於 target 的兩數索引值，回傳兩數索引值組成的容器（List 或 Object）。從題目給的限制及敘述中，可以得知必然只會有一組要求符合的結果，沒有規定回傳資料的順序。

開始實作

在理解完題目與條件之後，那我們下一步就開始「#初探直覺解」並且一起嘗試「#刻意優化」的過程：

方法 ①：雙層迴圈

這個題目回到要求來看：

從 nums 中找出兩數相加等於 target 的兩數索引值

需要同時找到兩件元素：(1) 兩數 (2) 索引值 ，並且去定義出相等的條件，初步的邏輯如下：

if num1 + num2 == target:
    return [i, j]

再來就是該怎麼去找出 num1 、 num2 和 i、j 索引值呢？這裡我們第一種方法想到的是用索引值進行兩個迴圈的迭代：

for i in ragne(len(nums)):
    for j in ragne(len(nums)):
        num1 = nums[i]
        num2 = nums[j]

這樣一來就可以得到 nums 所有的任兩數組合，分別指定到 num1 和 num2 變數中。只是這個寫法有一個小疑慮，這個寫法會把 nums 中的 任兩數的排列組合 都找出來，這裡的任兩數會包含重複出現（也就是自己跟自己也是一種組合）。不過，根據題目要求「任兩數」是「任意兩個不重複的數」進行相加，因此可以改寫成：

for i in ragne(len(nums)):
    for j in ragne(i+1, len(nums)):
        num1 = nums[i]
        num2 = nums[j]

第二個迴圈只需要針對第一個迴圈還沒有計算過的位置繼續往後即可。

那我們先用 Python 實作看看

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

也可以用 JavaScript 復刻一次

var twoSum = function(nums, target) {
    for(var i = 0 ; i < nums.length ; i++){
        for(var j = i ; j < nums.length ; j++ ){
            if(  nums[i] + nums[j]  == target ){
                return [i, j];
            }
        }
    }
};

方法 ②：一層迴圈 + 雜湊表（Hash Table）

第一種方法我們利用兩個迴圈把任兩數的排列組合全部找出來，第二個想法是能否 只使用一個迴圈 就解決這個問題呢？若只使用一個迴圈的話，那是必須要把某些資訊暫存起來。原本題目要求的是：

num1 + num2 == target

我們可以題目的要求轉個方向：

target - num1 = num2

如此一來，在一個迴圈中我們可以將 num1 暫存起來，並且去檢查已經存過的 num1 是否等於現在所需要的 num2。需要一個可以自定義 key-value 的資料結構來暫存 num1，這裡可以使用 Python 中的 dictionary 或是 JavaScript 中的 Object ，這種類似雜湊表（Hash Table）的資料結構。這個想法可以寫成這樣：

d = {}
num2 = target - num1
if num2 in d:
    return [i, j]

但因為需要 num1、num2 的索引值，所以需要暫存的資訊中，也要把索引值記錄下來：

d = {}
num1 = nums[i]
num2 = target - num1
if num2 in d:
    return [d[num2], i]
d[num2] = i

那我們先用 Python 實作看看

class Solution(object):
    def twoSum(self, nums, target):
        d = {}
        for i in range(len(nums)):
            num1 = nums[i]
            num2 = target - num1
            if num2 in d:
                return [d[num2], i]
            d[num1] = i

也可以用 JavaScript 復刻一次

var twoSum = function(nums, target) {
    var d = {};
    for(var i = 0 ; i < nums.length ; i++){
        var num1 = nums[i];
        var num2 = target - num1;
        if(d[num2] >= 0){
            return [d[num2], i]
        d[num1] = i;
    }
};

方法 ③：半個迴圈 + 雙指針（Two Pointer）

第三種方法我們使用雙指針（Two Pointer）的方法來實現，雙指針簡單來說就是自定義位置指向元素，移動指標位置來調整想要從容器中取出的數值：

i = 0
j = len(nums) - 1
while ...:
    if ...:
        i = i + 1
    else:
        j = j - 1

根據題目要求，這裡可以利用兩個指針計算兩個元素和，不符合則往中間移動直到滿足題目要求：

while (nums[i] + nums[j] != target):
    if (nums[i] + nums[j] > target):
        j = j - 1
    else:
        i = i + 1

那我們先用 Python 實作看看

class Solution(object):
    def twoSum(self, nums, target):
        i = 0
        j = len(nums) - 1
        
        while (nums[i] + nums[j] != target):
            if (nums[i] + nums[j] > target):
                j = j - 1
            else:
                i = i + 1
                
        return [i, j]

也可以用 JavaScript 復刻一次

var twoSum = function(nums, target) {
    
    var i = 0;
    var j = nums.length - 1;
    while (nums[i] + nums[j] != target){
        if (nums[i] + nums[j] > target)
            j = j - 1
        else
            i = i + 1
    }

    return [i, j]
};

但是這個方法跑測試案例的時候會過，但實際上在執行的時候是不會過的。原因是這裡雙指針的移動必須是原始資料已排序的情況下才能這樣動，所以其實更適合的是 167. Two Sum II - Input array is sorted 情境。若想將該題調整的話，記得也要將原始的索引值也要記錄下來才可以，過程上會比較麻煩，可以參考以下做法：

nums1 = nums[i]
nums2 = nums[j]

i = raw_nums.index(nums1)
if nums1 == nums2:
    j = raw_nums[i+1:].index(nums2)
    return [i, i+1+j]
j = raw_nums.index(nums2)
return [i, j]

反思沉澱

進入「一個題目」的解題過程時，可以分成「#動手之前先思考 → #初探直覺解 → #刻意優化 → #舉一反三」幾個階段的優化過程。這個題目有兩件事情是值得注意的：

1. 方法一到方法三的持續優化
2. Python 和 JavaScript 語法轉換

「如何最大化一個題目的效益」也是刷題過程中重要的關鍵，如何從一個盡可能地持續迭代、持續優化並且思考沈澱，讓你從一個題目掌握到更深更廣的效益。雖然只有一個題目，不過我們就學習到兩種語言共計六種寫法，這就是所謂的最大化一個題目中可以掌握的方法與技巧。

舉一反三看看相似題

最後可以從題目提供的相似題看一下有哪些類似的題目，適合作為你下一個嘗試的練習：

• 15. 3Sum
• 18. 4Sum
• 167. Two Sum II - Input array is sorted
• 170. Two Sum III - Data structure design
• 653. Two Sum IV - Input is a BST

嗨，大家好！我是維元，一名擅長網站開發與資料科學的雙棲工程師，斜槓於程式社群【JSDC】核心成員及【資料科學家的工作日常】粉專經營。目前在 ALPHACamp 擔任資料工程師，同時也在中華電信、工研院與多所學校等單位持續開課。擁有多次大型技術會議講者與競賽獲獎經驗，持續在不同的平台發表對 #資料科學、 #網頁開發 或 #軟體職涯 相關的分享，邀請你加入 訂閱 接收最新資訊。